import re
class Stack(object):
    # 初始化栈为空列表
    def __init__(self):
        self.items = []

    # 判断栈是否为空，返回布尔值
    def is_empty(self):
        return self.items == []

    # 返回栈顶元素
    def peek(self):
        return self.items[len(self.items) - 1]

    # 返回栈的大小
    def size(self):
        return len(self.items)

    # 把新的元素堆进栈里面（程序员喜欢把这个过程叫做压栈，入栈，进栈……）
    def push(self, item):
        self.items.append(item)

    # 把栈顶元素丢出去（程序员喜欢把这个过程叫做出栈……）
    def pop(self):
        return self.items.pop()
    def items(self):
        return self


# if __name__ == '__main__':
#     # 初始化一个栈对象
#     my_stack = Stack()
#     # 把'h'丢进栈里
#     my_stack.push('h')
#     # 把'a'丢进栈里
#     my_stack.push('a')
#     # 看一下栈的大小（有几个元素）
#     print(my_stack.size())
#     # 打印栈顶元素
#     print(my_stack.peek())
#     # 把栈顶元素丢出去，并打印出来
#     print(my_stack.pop())
#     # 再看一下栈顶元素是谁
#     print(my_stack.peek())
#     # 这个时候栈的大小是多少？
#     print(my_stack.size())
#     # 再丢一个栈顶元素
#     print(my_stack.pop())
#     # 看一下栈的大小
#     print(my_stack.size)
#     # 栈是不是空了？
#     print(my_stack.is_empty())
#     # 哇~真好吃~
#     print('Yummy~')
#定义运算符优先级
ops_level = {
    '+':1,
    '-':1,
    '*':2,
    '/':2,
}

sstring = 'a+b*c+(d*e+f)*g'
x = re.findall('\D',sstring)
print(type(x),x)

if __name__ == '__main__':
#
#临时存储运算符的栈S2（含一个结束符号），一个作为输入逆波兰式的栈S1（空栈）
#逻辑
# 1.如果是运算数直接压入S1 (else )
# 1.如果是运算符
#     1（直接压入
#     2.）(之间的运算符，逐个出栈，依次压入栈s2
#     3.如果不是（、）、则判断栈顶元素为（则直接压入，不是则判断。如果小于优先级，直接将其压入S2。直到优先级大于等于栈顶元素
# 2.遍历完以后检查S1是否为空，不为空则全部压入S2

    S1 = Stack()
    S2 = Stack()
    for i in range(len(x)):

        if x[i] == '(':
            S2.push(x[i])
        elif x[i] == ')':
            while S1.size() > 0:
                s1pop = S1.pop()
                if s1pop == '(':
                    break
                else:
                    S2.push(s1pop)
        elif x[i] in ['+','-','*','/']:
            while S1.size() > 0:
                s1_peek = S1.peek()
                if ops_level(s1_peek1) < ops_level(x[i]):
                    S1.push(x[i])
                else:
                    S2.push(S1.pop())
    if S1.size() == 0:
        print(S2.items)
    else:
        while S1.size() > 0:
            s1_pops = S1.pop()
            S2.push(s1_pops)
        print(S2.items)












